import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-11-27
 * Time: 22:00
 */
public class Quicksorting {


        public static void sort(int[] arr, int left, int right) {
            if (left >= right || left >= arr.length || right < 0) return;
            int pos = arr[left]; // 挖坑，保存基准值
            int i = left, j = right;
            while (i < j) {
                // 从右侧开始，找到小于基准值的数
                while (i < j && arr[j] >= pos) {
                    j--;
                }
                if (i < j) {
                    arr[i] = arr[j]; // 将小于基准值的数填到左边坑中
                    i++;
                }
                // 从左侧开始，找到大于基准值的数
                while (i < j && arr[i] <= pos) {
                    i++;
                }
                if (i < j) {
                    arr[j] = arr[i]; // 将大于基准值的数填到右边坑中
                    j--;
                }
            }
            arr[i] = pos; // 将基准值填回坑中
            System.out.println(Arrays.toString(arr));
            sort(arr, left, i - 1); // 递归排序左半部分
            sort(arr, i + 1, right); // 递归排序右半部分
        }

        public static void main(String[] args) {
            int[] arr = new int[]{56, 1, 88, 66, 35, 7, 6, 2,8};
            sort(arr, 0, arr.length - 1);

    }

}
